package org.example;

public class Test3 {
    //leetcode 76 最小覆盖子串 https://leetcode.cn/problems/minimum-window-substring/description/
    public String minWindow(String s, String t) {
        int n1 = s.length(), n2 = t.length();
        int slow = 0, fast = 0, start = 0, end = 0, kinds = 0, ret = Integer.MAX_VALUE;
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];
        for (char c : t.toCharArray()) {
            hash2[c - 'A']++;
        }
        while (fast < n1) {
            while (fast < n1 && kinds < n2) {
                char c = s.charAt(fast++);
                if (hash2[c - 'A'] != 0 && ++hash1[c - 'A'] <= hash2[c - 'A']) kinds++;
            }
            while (kinds >= n2) {
                char c = s.charAt(slow++);
                if (fast - slow + 1 < ret) {
                    ret = fast - slow + 1;
                    start = slow - 1;
                    end = fast;
                }
                if (hash2[c - 'A'] != 0 && hash1[c - 'A']-- == hash2[c - 'A']) kinds--;
            }
        }
        if (start == end) return "";
        return s.substring(start,end);
    }

    public static void main(String[] args) {
        Test3 test3 = new Test3();
        String s = test3.minWindow("ADOBECODEBANC","ABC");
        System.out.println(s);
        System.out.println(666);
    }
}
